package cn.hy.today;

import java.util.Arrays;

// 得到山形数组的最少删除次数
class Solution_1671 {


    // 由于我们需要找出最长的「山形状数组」，并且 nums[0..i] 和 nums[i..n−1]
    // 这两部分是互相独立的，那么我们只需要找出 nums[0..i] 中以 nums[i] 结束的最长严格递增子序列，
    // 以及 nums[i..n−1] 中以 nums[i] 开始的最长严格递减子序列即可。
    // 对于严格递减子序列的部分，我们可以把数组 nums 进行反转，
    // 这样就从求解后缀的最长严格递减子序列，变成求解前缀的最长严格递增子序列了。
    public int minimumMountainRemovals(int[] nums) {
        int n = nums.length;
        int[] pre = getLISArray(nums);
        int[] reverse = reverse(nums);
        int[] suf = getLISArray(reverse);
        suf = reverse(suf); // 结果还需要逆序一次
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (pre[i] > 1 && suf[i] > 1) { // 最少是3
                ans = Math.max(ans, pre[i] + suf[i] - 1);
            }
        }
        return n - ans;
    }

    private int[] getLISArray(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        return dp;
    }

    private int[] reverse(int[] nums) {
        int n = nums.length;
        int[] reverse = new int[n];
        for (int i = 0; i < n; i++) {
            reverse[i] = nums[n - i - 1];
        }
        return reverse;
    }
}